#include "Automatas.h"

void FiniteStateMachine::addAsFinalState(int state)
{
	finalStates.push_back(state);
}

void FiniteStateMachine::addTransition(int state1, int state2, char symbol)
{
	tNodo n;
	n.simbol = symbol;
	n.state = state2;

	states[state1].push_back(n);
	_alphabet.insert(symbol);
}

int FiniteStateMachine::addState()
{
	vector<tNodo> v;
	states.push_back(v);

	return states.size()-1;
}

//---------------------------------------------------------------

DeterministicFiniteAutomaton::DeterministicFiniteAutomaton(int amountOfStates)
{
	finalStates.resize(0);

	states.resize(amountOfStates);

	for (int i=0; i<amountOfStates; i++)
		states[i].resize(0);
}

int DeterministicFiniteAutomaton::transition(int state, char symbol)
{
	typedef vector<tNodo> NodeVector;
	const NodeVector& transitions = states[state];

	for (NodeVector::const_iterator it = transitions.begin(); it != transitions.end(); ++it)
	{
		if (it->simbol == symbol)
			return it->state;
	}

	return -1;
}

bool DeterministicFiniteAutomaton::recognize(string word)
{
	int state = 0;
	for (int i=0; i < word.length() && state != -1; i++)
		state = transition(state, word.at(i));
   
	return isFinal(state);
}

bool DeterministicFiniteAutomaton::isFinal(int state)
{
	return find(finalStates.begin(), finalStates.end(), state) != finalStates.end();
}

//---------------------------------------------------------------

NondeterministicFiniteAutomaton::NondeterministicFiniteAutomaton(int amountOfStates)
{
	finalStates.resize(0);
	
	lambdaTransitions.resize(amountOfStates);

	states.resize(amountOfStates);

	for (int i=0; i<amountOfStates; i++)
		states[i].resize(0);
}

int NondeterministicFiniteAutomaton::getSize()
{
	return states.size();
}

vector<int> NondeterministicFiniteAutomaton::transition(int state, char symbol)
{
	vector<int> res;

	for (int i=0; i<states[state].size(); i++)
		if (states[state].at(i).simbol == symbol)
			res.push_back(states[state].at(i).state);

	return res;
}

vector<int> NondeterministicFiniteAutomaton::lambda(int state)
{
	return lambdaTransitions[state];
}

bool NondeterministicFiniteAutomaton::recognize(string word) 
{
	vector<bool> macrostate;
	macrostate.resize(getSize());
	macrostate[0] = true;
	macrostate = lambda_closure(macrostate);

	for(int i=0; i<word.length(); i++)
		macrostate = transition(macrostate,word.at(i));
		
	return isFinal(macrostate);
}

vector<bool> NondeterministicFiniteAutomaton::lambda_closure(vector<bool>state)
{
	vector<bool> result;
	bool change = true;
	while (change) {
		change = false;
		for (int i=0; i < state.size(); i++) if(state[i]){
			vector<int> lambdaPrima = lambda(i);
			for(int j=0; j<lambdaPrima.size(); j++){
				if (!state[lambdaPrima[j]]) change = true;
				state[lambdaPrima[j]] = true;
			}
		}
	}
	result = state;

	return result;
}

vector<bool> NondeterministicFiniteAutomaton::transition(vector<bool> state, char symbol) 
{
	vector<bool> result;
	result.resize(state.size());
	
	for(int i=0; i<state.size(); i++) if(state[i]){
		vector<int> list = transition(i,symbol);
		for(int j=0; j<list.size(); j++) result[list[j]] = true;
	}

	result = lambda_closure(result);
	return result;
}

NondeterministicFiniteAutomaton* NondeterministicFiniteAutomaton::o(NondeterministicFiniteAutomaton* automata)
{
	NondeterministicFiniteAutomaton* res = new NondeterministicFiniteAutomaton(this->getSize() + automata->getSize() + 2);
	
	res->addLambdaTransition(0, 1);
	res->addLambdaTransition(0, 1+this->getSize());
	
	res->copyStartingOn(1, this);
	res->copyStartingOn(1+this->getSize(), automata);
	
	res->addLambdaTransition(this->finalStates[0]+1, res->getSize() - 1);
	res->addLambdaTransition(automata->finalStates[0]+this->getSize()+1, res->getSize() - 1);
	res->addAsFinalState(res->getSize() - 1);
	
	return res;
}
//Copio todos los estados de <automata> en <this>, pero a partir de la posicion <offset> de <this>
void NondeterministicFiniteAutomaton::copyStartingOn(int offset, NondeterministicFiniteAutomaton* automata)
{
	//Copio todos los estados y sus transiciones comunes
	for(int i = 0; i < automata->states.size(); i++){
		for(int j = 0; j < automata->states[i].size(); j++){
			this->addTransition(i+offset, automata->states[i][j].state+offset, automata->states[i][j].simbol);
		}
	}
	//Copio todos los estados y sus transiciones lambda
	for(int i = 0; i < automata->lambdaTransitions.size(); i++){
		for(int j = 0; j < automata->lambdaTransitions[i].size(); j++){
			this->addLambdaTransition(i+offset, automata->lambdaTransitions[i][j]+offset);
		}
	}
}

NondeterministicFiniteAutomaton* NondeterministicFiniteAutomaton::concat(NondeterministicFiniteAutomaton* automata)
{
	NondeterministicFiniteAutomaton* res = new NondeterministicFiniteAutomaton(this->getSize() + automata->getSize());
	
	res->copyStartingOn(0,this);
	res->copyStartingOn(this->getSize(), automata);

	res->addLambdaTransition(this->finalStates[0], this->getSize());

	res->addAsFinalState(res->getSize() - 1);
	
	return res;
}

//----------------------------------------------------------------------------------------
NondeterministicFiniteAutomaton* NondeterministicFiniteAutomaton::kleeneClosure()
{
	NondeterministicFiniteAutomaton* res = new NondeterministicFiniteAutomaton(this->getSize() + 2);
	
	res->copyStartingOn(1,this);

	res->addLambdaTransition(0, 1);
	res->addLambdaTransition(this->finalStates[0] + 1, 1);
	res->addLambdaTransition(0, res->getSize()-1);
	res->addLambdaTransition(this->finalStates[0] + 1, res->getSize()-1);

	res->addAsFinalState(res->getSize() - 1);
	
	return res;
}

//----------------------------------------------------------------------------------------
NondeterministicFiniteAutomaton* NondeterministicFiniteAutomaton::positiveClosure()
{
	NondeterministicFiniteAutomaton* res = new NondeterministicFiniteAutomaton(this->getSize() + 2);
	
	res->copyStartingOn(1,this);

	res->addLambdaTransition(0, 1);
	res->addLambdaTransition(this->finalStates[0] + 1, 1);
	res->addLambdaTransition(this->finalStates[0] + 1, res->getSize()-1);

	res->addAsFinalState(res->getSize() - 1);
	
	return res;
}

//----------------------------------------------------------------------------------------
NondeterministicFiniteAutomaton* NondeterministicFiniteAutomaton::withOptionalOperand()
{
	NondeterministicFiniteAutomaton* res = new NondeterministicFiniteAutomaton(this->getSize());
	
	res->copyStartingOn(0,this);
	res->addLambdaTransition(0, res->getSize()-1);
	res->addAsFinalState(res->getSize() - 1);
	
	return res;
}
//----------------------------------------------------------------------------------------
NondeterministicFiniteAutomaton* NondeterministicFiniteAutomaton::acceptingChar(char aCharacter)
{
	NondeterministicFiniteAutomaton* res = new NondeterministicFiniteAutomaton(2);
	
	res->addTransition(0,1,aCharacter);
	res->addAsFinalState(1);
	
	return res;
}

//----------------------------------------------------------------------------------------
NondeterministicFiniteAutomaton* NondeterministicFiniteAutomaton::acceptingDot()
{
	NondeterministicFiniteAutomaton* res = new NondeterministicFiniteAutomaton(2);
	
	for(char i='a'; i<='z'; i++)
		res->addTransition(0,1,i);

	for(char i='A'; i<='Z'; i++)
		res->addTransition(0,1,i);

	for(char i='0'; i<='9'; i++)
		res->addTransition(0,1,i);

	res->addTransition(0,1,' ');
	
	res->addAsFinalState(1);
	
	return res;
}

void NondeterministicFiniteAutomaton::print(){
	cout << "-------" << endl;
	for(int i = 0; i < this->states.size(); i++){
		for(int j = 0; j < this->states[i].size(); j++){
			cout << "Estado: " << i << " Transicion a: " << this->states[i][j].state << " Simbolo: " << this->states[i][j].simbol << endl;
		}
	}
	for(int i = 0; i < this->lambdaTransitions.size(); i++){
		for(int j = 0; j < this->lambdaTransitions[i].size(); j++){
			cout << "Estado: " << i << " Transicion lambda a: " << this->lambdaTransitions[i][j] << endl;
		}
	}
	cout << "-------" << endl;
}
bool NondeterministicFiniteAutomaton::isFinal(vector<bool> state)
{
	for(int i=0; i<state.size(); i++) if(state[i])
		if(isFinal(i)) return true;
	 	
	return false;
}

bool NondeterministicFiniteAutomaton::isFinal(int state)
{
	return find(finalStates.begin(), finalStates.end(), state) != finalStates.end();
}

void NondeterministicFiniteAutomaton::addLambdaTransition(int state1, int state2)
{
	lambdaTransitions[state1].push_back(state2);
}
